1. Field of the Invention
The present invention relates to a file system, and more particularly to a file system that frequently performs a file search.
2. Description of the Related Art
In general, a file system manages directories and files in the form of a tree. According to such a tree-type file system, nodes of a root part corresponds to root directories, each node other than a leaf corresponds to a directory, and each leaf corresponds to a file or an empty directory. In such a file system, a file is searched for by separating a given route based on directory delimiters and then by matching the given route with corresponding nodes in a sequence from a route node. For example, when there is a route of “/A/B/C,” the file system executes a file searching operation in such a manner that the file system separates nodes into nodes A, B and C, finds node A from among route nodes, finds node B from among nodes contained in node A when having found node A, and then finds node C from among nodes contained in node B when having found node B. When the file system fails in a search even once while performing the file searching operation, it is determined that the corresponding file is a nonexistent file.
A file searching procedure based on a File Allocation Table (FAT) file system, which is currently in general use, will now be described in more detail. According to the FAT file system, first, a root directory file must be read in order to find nodes contained in a root node. The root directory file represents a file that includes information about nodes included in a root directory and the attributes of the root directory. When a root directory file cannot all be stored in one FAT block (i.e., a cluster) because the root directory file is too large, it is necessary to read all blocks in which the root directory file has been stored. In this case, blocks storing the root directory file can be found by means of a look-up table (i.e., FAT table) of the FAT file system. The FAT table stores information about whether each block is in use, and a list of blocks when a file has been stored over the blocks.
When a directory file has been read, the FAT file system searches the read directory for a desired file. In this case, generally, since nodes and/or files (hereinafter, “entries”) included in a directory are not arranged, a desired entry must be searched for in a linear searching scheme. When the desired entry has been searched for, data of the searched entry is read from a block storing the data corresponding to the searched entry. If the read entry's data corresponds to data of a different directory, it is necessary to again read a file of the corresponding directory. Therefore, until a given route has been found, a procedure of reading a directory file and finding the entry of a desired directory is repeatedly performed.
Once a desired file has been found, information about a data block storing data of the desired file can be understood, so that it is possible to perform a file processing operation such as a writing or reading. If a file is too large to be stored in one block, one or more different empty blocks can additionally be used. In this case, when a file pointer moving instruction, such as a reading, writing or searching, is issued, the file system moves a file point by means of the FAT table so as to find a next block, similar to when reading a directory file.
The recent file systems including New Technology File System (NTFS) and 3rd EXTended file system (EXT3) further have various functions to solve such a FAT defect. For example, the recent file systems additionally provide a method of relieving the restriction of a file size, or a supplementary structure to rapidly search for a directory entry. However, since even such recent file systems have structures similar to that of the aforementioned FAT file system, the recent file systems also perform a file searching operation in a manner similar to that of the FAT file system. That is, the recent files systems also are configured in the form of a tree in which a root directory, a plurality of directories and a plurality of files included in each directory are arranged.
Generally, a file system is implemented in a block device having a block-type memory structure, such as a hard disk or flash memory. Therefore, in this case, in order to search for a desired file, a block reading operation with respect to one or more directory files must be performed as many times as the number of directory nodes included in a file route. Generally, it takes a long time to read a specific memory block in a storage device, such as a hard disk or flash memory. Particularly, in the case of the hard disk, if blocks therein are discontinuous, it takes a very long time to access each block, thereby taking a longer time to read the blocks in the hard disk than in the flash memory. As described above, conventional file systems have a problem in that they take a long time to search for a desired file.